package Tree;

import java.util.Stack;

public class ConstructMaximumBinaryTree {
    public static void main(String[] args) {

    }

    public TreeNode constructMaximumBinaryTree(int[] nums){
        Stack<TreeNode> stack = new Stack<>();

        for(int num : nums){
            TreeNode curNode = new TreeNode(num);
            // 如果当前节点大，证明刚才的节点应该在左边，则找到之前构建时的顶点
            while(!stack.isEmpty() && stack.peek().val < num){
                curNode.left = stack.pop();
            }
            if(!stack.isEmpty()){
                stack.peek().right = curNode;
            }
            stack.push(curNode);
        }

        return stack.firstElement();
    }

}
